package graphs;

import java.util.*;

public class GraphGenerator {
    //通过二维数组创造一个图
    // matrix所有的边
    //N*3的矩阵
    //[权重,出发点的值/编号,到达点的值/编号]
    public static Graph createGreaph(Integer[][] matrix){
        Graph graph=new Graph();
        for (int a=0;a<matrix.length;a++){
            //首先获得Node的信息
            Integer weight=matrix[a][0];
            Integer from=matrix[a][1];
            Integer to=matrix[a][2];
            //判断图中是否已经包含两个点 如果没有 则添加
            if (!graph.nodes.containsKey(from)){
                graph.nodes.put(from,new Node(from));
            }
            if (!graph.nodes.containsKey(to)){
                graph.nodes.put(from,new Node(to));
            }

            //建立边的信息
            Node fromNode=graph.nodes.get(from);
            Node toNode=graph.nodes.get(to);

            Edge newEdge=new Edge(weight,fromNode,toNode);
            fromNode.next.add(toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
        return graph;
    }

    //实现一个图的宽度优先遍历 从某个节点开始  利用队列
    public static void printByWide(Node node){
        Queue<Node> nodeQueue=new LinkedList<>();
        HashSet<Node> nodeSet=new HashSet<>();
        nodeQueue.add(node);
        nodeSet.add(node);
        while (!nodeQueue.isEmpty()){
            node=nodeQueue.poll();  //先把当前元素出队
            System.out.print(node.value);
            if (node.next!=null){
                for (int a=0;a<node.next.size();a++){
                    if (!nodeSet.contains(node.next.get(a))){   //如果队列中不包括当前节点  则可以遍历
                    nodeQueue.add(node.next.get(a));
                    nodeSet.add(node.next.get(a));
                    }
                }
            }
        }
    }

    //实现一个图的深度优先遍历 利用栈
    public static void printByDept(Node node){
        if (node==null){
            return;
        }
        Stack<Node> stack=new Stack<>();
        HashSet<Node> nodeSet=new HashSet<>();
        stack.add(node);
        nodeSet.add(node);
        while (!stack.isEmpty()){
            Node n=stack.pop();  //先把当前元素出队
            System.out.print(n.value);
            for(Node node1: n.next){
                if (!nodeSet.contains(node1)){
                    stack.push(node1);
                    nodeSet.add(node1);
                }
            }
        }
    }

    //把图中点用拓扑排序的形式返回
    public static List<Node> sortedTopology(Graph graph){
        //key  某个节点
        //value  当前节点的入度
        //建立一个队列 入度为0的点加入队列  也就是找到第一个点
        Queue<Node> nodeQueue=new LinkedList<>();
        for (Node node : graph.nodes.values()){
            if (node.in==0){
                nodeQueue.add(node);
            }
        }
        //拓扑排序的结果 依次加入集合中
        List<Node> nodeList=new ArrayList<>();
        while (!nodeQueue.isEmpty()){
            Node cur=nodeQueue.poll();
            nodeList.add(cur);
            for (Node next: cur.next){
                if (next.in == 0){
                    nodeQueue.add(next);
                }
            }
        }
        return nodeList;
    }

    //最小生成树算法  在保证所有点都联通的情况下  尽可能的删掉权值大的边 使得剩下边的权值尽可能小
    public static void getMinTree(Graph graph){
        Node[] nodes=(Node[]) graph.nodes.values().toArray();
        int listNum=graph.nodes.size();  //获得所有的节点的个数
        HashMap<Node,ArrayList<Node>> hashMap=new HashMap<>();
       /* PriorityQueue<Edge> priorityQueue=new PriorityQueue<>(new EdgeCom());*/
    }

    //根据权值排序
    public static class EdgeCom implements Comparator<Edge>{
        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight-o2.weight;
        }
    }

    //单源最短路径问题
    public static HashMap<Node,Integer> dijkstar1(Node from){
        //此时从from出发到所有点的最小距离
        //key：从from出发到达key
        //value:从from出发到达key的最小距离
        //如果在表中，如果T没有记录，含义是从from出发到T这个点的距离为正无穷
        HashMap<Node,Integer> distanceMap=new HashMap<>();
        distanceMap.put(from,0);
        //已经求过距离的节点  存在selectNodes中，不要再碰
        HashSet<Node> selectNodes=new HashSet<>();

        //在distanceMap中找到权值最小的节点 但是除了已经被确定selectNodes的点
        Node minNode=getMinDistanceAndUnselectedNode(distanceMap,selectNodes);
        while (minNode !=null){
            int distance=distanceMap.get(minNode);
            for (Edge edge : minNode.edges){
                Node toNode=edge.to;
                if (!distanceMap.containsKey(toNode)){
                    distanceMap.put(toNode,distance + edge.weight);
                }else {
                    distanceMap.put(edge.to,
                            Math.min(distanceMap.get(toNode),distance+edge.weight));
                }
            }
            selectNodes.add(minNode);
            minNode=getMinDistanceAndUnselectedNode(distanceMap,selectNodes);
        }
        return distanceMap;
    }

    public static Node getMinDistanceAndUnselectedNode(HashMap<Node,Integer> distanceMap,HashSet<Node> touchNodes){
        Node minNode = null;
        int minDistance = Integer.MIN_VALUE;
        for (Map.Entry<Node,Integer> entry : distanceMap.entrySet()){
            Node node = entry.getKey();
            int distance = entry.getValue();
            if (!touchNodes.contains(node) && distance<minDistance){
                minNode = node;
                minDistance=distance;
            }
        }
        return minNode;
    }


}
